1. Field of the Invention
This invention relates to security passwords and more particularly to a method and system for proactively validating passwords.
2. Description of the Related Art
Poorly chosen passwords continue to be a major cause of security breaches. The increasing popularity of such products as the Unix Operating System and the Kerberos Authentication Protocol in commercial environments accentuate this problem, as both are vulnerable to security breaches by dictionary attacks which search for poor passwords.
Given the choice, most users choose passwords from a "likely password" key space, K.sub.1, that is a small fraction of the entire key space, K, available to them. This smaller key space is typically composed of bad passwords and bad noisy passwords. Bad passwords are those chosen from natural language, jargon, acronyms, dates, or other numeric series, and/or derivatives thereof. Bad noisy passwords consist of a bad password plus noise (e.g. tiger2 or compquter). The small size of K.sub.1, facilitates breaches of security through exhaustive searches of the "likely password" key space, which can be performed using conventional techniques and technologies that are well known in the art. For instance, in the Unix operating system (see Morris, R. and K. Thompson. "Password security: A case history", Communications of the ACM, 22(11), November 1979), user passwords are transformed using a one way function based upon the data encryption standard (DES) (see Data Encryption Standard, National Bureau of Standards, Federal Information Processing Standards, Publication No. 46-1 (Jan. 15, 1977)), and then stored in a password file that is usually accessible to a number of individuals and is in all cases accessible to the administrators of the system to which the password provides access. As the one way function itself is not secret, an adversary can methodically apply this function to all words in K.sub.1, and then compare the results to those in the password file. The Kerberos Authentication Protocol (see Kohl, J. C. Neuman and J. Steiner, "The Kerberos Network Authentication Service", MIT Project Athena (Oct. 8, 1990) Version 5, Draft 3), is also vulnerable to such dictionary attacks as, for reasons not relevant here, the protocol makes it possible for an adversary having a user password to request server access to encrypted messages. Further, by eavesdropping on the network, the adversary can also obtain additional encrypted messages which can be decrypted using the same exhaustive key search technique on K.sub.1.
The size of the key space that can be searched efficiently by an adversary is much larger than is usually believed by most users. Karn and Feldmeier have discussed the size of the key space that can be searched using conventional techniques and technology. (See Karn, P. R. and D. C. Feldmeier, "UNIX password security--Ten years later", Advances in Cryptology--CRYPTO '89, G. Brassard (Ed.) Lecture Notes in Computer Science, Springer Verlag, 1990). Although this discussion is directed towards UNIX password security, the Karn and Feldmeier analysis is widely applicable to typical systems which have artificially small password key space and are therefore susceptible to a key search attack. Protection against such attacks can be enhanced by either altering the system itself, for instance, as proposed by Bellovin and Merritt to secure Kerberos (see Bellovin, S. and M. Merritt, "Encrypted Key Exchange" IEEE Computer Society Symposium on Security and Privacy, May 1992, Oakland, Calif.) or enlarging the size of the likely password key space K.sub.1 until it approaches the size of K, where K is very large. Another approach to improving password security is to establish a system to select a random password of key space K for the user. This later approach, however, is particularly unfriendly to the user and can lead to users maintaining a written ledger of their passwords to avoid having to memorize a long and arbitrarily selected password.
A proactive password checker is often a component of a password changing program. The checker attempts to validate the quality of a password chosen by the user before making the change. In addition to checking the size of the password and whether the password is derived from commonly known user related information, the heart of a conventional proactive password checker is the maintenance of a dictionary of bad passwords against which the selected password is checked.
One problem with conventional checkers is that the dictionary of passwords can require tens of megabytes of storage space. Another problem is that in any distributed processing environment the dictionary may have to be replicated on several servers or processing units. A further problem with such systems is that the time to search the dictionary increases logarithmically with the number of bad passwords being stored within the dictionary. Further still, using such a dictionary to filter out bad noisy passwords is difficult.
Proactive password checking systems are based on the philosophy that, with sufficient guidance, users can select passwords from a fairly large key space, which are not likely to be guessed or otherwise broken in the course of a key search attack. Conventional proactive password checking systems interact with the user, explain the type of passwords that are desirable, check for the appropriate password size and mix of upper and lower case letter characters, numerals and special characters, check if the password is drawn from the user's name or other user specific information, and finally check if the password is in a dictionary of bad passwords. (see Bishop, M., "Proactive Password Checking", 4th Workshop on Computer Security Incident Handling, August 1992).
Two conventional proactive password checking systems have been proposed to reduce the storage space required to check a selected password against a dictionary of bad passwords. Both follow conventional pattern matching frameworks (see Ganesan, R. and A. Sherman, "Statistical Techniques for Language Recognition: An Introduction and Guide for Cryptanalysis", TR CS-93-2, University of Maryland, 1993). Using this framework a set of characteristics, C, is first extracted from a given dictionary of bad passwords. To save space, C must be smaller than the dictionary itself. Next, a test, T.sub.v, is used to determine if a given password has characteristics similar to C. These checking systems differ however in the characteristics, C, extracted from the dictionary and consequently the test, T.sub.v, used to determine whether or not the selected password is good or bad.
The Nagle system selects a three dimension boolean matrix, B [i, j, k] as the set of characteristics, C, where i, j and k correspond to the indices in a set. Next, the bad password dictionary is scanned. Each time a sequence of three consecutive characters, henceforth referred to as trigrams, is observed the corresponding bit in the boolean array is set. For example, the password abcd1 will cause B [a,b,c], B [b,c,d] and B [c,d,other] to be set to 1. By scanning all the passwords in the dictionary many such bits will be set. After completion of the dictionary scan off-line (i.e., in non-real time), all trigrams from the bad passwords are extracted. The proposed password is validated on-line (i.e., in real time) as a good password only if at least two trigrams do not have corresponding bits set in B. The Nagle technique does an excellent job of screening most bad passwords. However, it does a poor job of screening bad noisy passwords.
The OPUS checking system is based on Bloom filters (see Spafford, E. H., "OPUS: Preventing Weak Password Choices", Purdue Technical Report CSC-TR 92-028, June 1991) which are commonly used in spelling checkers. Using the OPUS approach, B [n] is selected as a boolean array of size N. Next, a set of hash functions H.sub.1, H.sub.2, . . . , H.sub.D is selected. For a given password, each hash function assigns a number in the range 0 . . . N. Each bad password in the dictionary is run through all hash functions and for each of the hash functions a number, n.sub.i, is generated, and the bit in the boolean array B [n.sub.i ], is set. A selected password is then run through the hash functions generating n.sub.1, n.sub.2, . . . n.sub.D. If any of the boolean array bits generated by the selected password are not within the boolean array bits set by the bad passwords, then the selected password is validated. If all the generated boolean array bits are within the set, then it is likely that the selected password is in the dictionary and therefore should not be validated. However, there is a probability with the OPUS approach that a good password may be mistakenly identified as being in the dictionary of bad passwords. By increasing the size of the boolean array this probability can be reduced. Also appropriate selection of the hash functions will improve the accuracy of the OPUS system. By its nature, the OPUS approach will consistently recognize a selected password which is also a bad password in the selected dictionary of bad passwords. However, the OPUS approach does not recognize bad noisy passwords. It also requires a boolean array large enough to sufficiently reduce the probability that good passwords will be mistakenly identified as bad passwords. Because of the required size of the boolean array, reductions in the required storage capacity may be limited.
Thus, it is an object of the present invention to provide a method and system to validate a chosen password before the selection is finalized. It is a further object of the present invention to provide a method and system for performing such validation without the need to store a dictionary of bad passwords and/or bad noisy passwords. It is a still further object of this invention to provide a method and system for validation which does not require a large database of information to be stored on a server or other storage device for use in the validation process. It is another object of this invention to provide a method and system which can be utilized to quickly perform password validation. It is yet another objective of this invention to provide a method and system for proactively checking against bad noisy passwords without having to generate the bad noisy passwords on-line.
Additional objects, advantages and novel features of the invention will become apparent to those skilled in the art upon examination of the following as well as by practice of the invention. While the invention is described below with reference to preferred embodiments for proactive validation of passwords, it should be understood that the invention is not limited thereto. Those of ordinary skill in the art having access to the teachings herein will recognize additional applications, modifications and embodiments in other fields (including, but not limited to, those relating to smart cards, automatic tellers and automatic locks), which are within the scope of the present invention as disclosed and claimed herein and in which the present invention could be of significant utility.